package Offer2017;

/**
 * 链表中倒数第K个结点
 * Created by 雷文康 on 2017/12/31.
 */
public class Test15 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode p1 = new ListNode(2);
        ListNode p2 = new ListNode(3);
        ListNode p3 = new ListNode(4);
        head.next = p1;
        p1.next = p2;
        p2.next = p3;
        ListNode result = findLastK2(head, 1);
        if (result != null){
            System.out.println(result.value);
        } else {
            System.out.println(result);
        }
    }

    public static ListNode findLastK2(ListNode head, int K){
        if(head == null){
            return null;
        }
        ListNode p1 = head;
        ListNode p2 = head;
        int step = 0;
        while (p1.next != null){
            p1 = p1.next;
            step++;
            if (step >= K){
                p2 = p2 .next;
            }
        }
        if (step < K - 1){
            return null;
        }
        return p2;
    }

    public static ListNode findLastK(ListNode head, int K){
        if(head == null){
            return null;
        }
        ListNode p1 = head;
        ListNode p2 = head;
        for (int i = 1; i <= K - 1; i++) {
            if (p1.next != null){
                p1 = p1.next;
            } else {
                return null;
            }
        }
        while (p1.next != null && p2.next != null){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }
}
